FIG. 1 depicts a device 10 that includes a signature touch pad 20 that generates x-axis and y-axis positional information in response to being touched with a stylus or pen 30 at one or more points on the pad. In some systems, stylus 30 is active, e.g., is coupled to a battery to present a potential or charge on touch pad 20. In other systems, stylus 30 is passive, e.g., is a plastic or wooded stick, and touch pad 20 responds to physical force exerted by the tip of the stylus.
Touch pad 20 may be opaque, but preferably includes a liquid crystal display ("LCD"). An LCD touch pad can display the point presently touched by the stylus, as well as the locus of preceding touched points, as the stylus was dragged across the touch pad. For example, in FIG. 1, a user's signature 40 has been written on touch pad 20 and is displayed by a LCD in real time, e.g., as the signature is made. Device 10 can also be used to draw sketches, or other information on touch pad 20. However, as used herein, the term "signature" will refer to a user's written signature.
Device 10 includes an analog-to-digital ("A/D") converter and stylus detect circuitry, collectively 50, that digitizes analog positional data into digital (x,y) signature positional data. Thus, signature 40 is represented as a collection of digital (x,y) coordinates. (For ease of understanding, the x-axis and y-axis are depicted on touch pad 20.)
Device 10 includes a central processing unit ("CPU") 60 that receives the digitized data as a data stream of (x,y) positional information, referred to herein as signature data. Device 10 also includes internal read only memory ("ROM") and random access memory ("RAM"), shown collectively as 70. The signature data is stored in RAM, and may be processed by CPU 60, using software routine(s) stored in ROM. Frequently, the signature data or processed signature data is transmitted to a host system 80 over a cable or wireless communication link 90.
Device 10 typically has other capabilities as well. For example, U.S. patent application Ser. No. 08/853,955, entitled MODULAR SIGNATURE AND DATA-CAPTURE SYSTEM AND POINT OF TRANSACTION PAYMENT AND REWARD SYSTEM (filed May 9, 1997 and assigned to assignee herein) discloses a particularly advanced signature capture device 10 and associated systems.
As generated, the data stream consists of a given number of bytes and is uncompressed. For example, in uncompressed form, each (x,y) position point may comprise 4-bytes total, and the locus of positional data representing signature 40 may comprise a total of T bytes, uncompressed. However, to reduce RAM storage requirements, it is known in the art to store in ROM a data compression routine. Such a routine is executed by CPU 60 to compress the data stream, such that a signature (or image) requiring T bytes of storage in uncompressed format can now be stored in K.times.T bytes, where K&lt;1. The compression ratio represents the numerical reduction in size of the original data set. Thus if K=0.25, a 1000 byte data set may be reduced to 250 bytes upon compression, and the compression ratio is four.
The compressed data set eventually will be decompressed, perhaps by a CPU within host system 80 that executes a software decompression program stored within system 80. Ideally, the decompressed data represents an original data set that would have been stored had no compression being employed on the signature data stream.
For example, device 10 may be used in commercial transactions to facilitate credit card payment by users, perhaps at a grocery store. Host system 80 may, for example, store (compressed or uncompressed) a library of known genuine signatures for many users, including a true exemplar of signature 40. At time of payment at the grocery store, a user presenting a credit card will create signature 40 on device 10. Understandably, if the credit card is stolen, the user will not be able to create a genuine signature 40, only a forgery.
The signature data corresponding to signature 40 is transmitted typically in compressed form to host system 80. Host system 80 decompresses the signature data and compares the uncompressed data to previously stored data for the genuine signature for the user in question. Based upon the comparison, host system 80 communicates to the merchant at the point of transaction, often via link 90 and device 10, whether signature 40 is genuine or an apparent forgery. If genuine, the transaction proceeds, and if a potential forgery, the user will be asked for further identification, or to re-sign the signature, or the credit card being used may be confiscated.
Although adequate image resolution exists in the original signature data set, some resolution may be lost during compression. Because some data is thus lost, it may not always be possible to restore a faithful reproduction of the original sized signature. As a result, a decompressed reproduced signature can appear jagged and will may create verification problems when compared with the original signature.
Understandably, verification use of compressed signature data requires that when uncompressed, the original signature may be recovered with minimal distortion. However, so-called lossy compression techniques distort the original form of the signature data in the process of attempting to reduce the storable byte size. As a result, the original data set cannot be faithfully recovered or extracted from a lossy compressed data set. By contrast, lossless compression does not distort the original form of the data, and permits the original data set to be faithfully extracted using appropriate decompression techniques.
For example, U.S. Pat. No. 5,473,742 to Polyakov 1995) discloses a compression algorithm that provides a compression ratio of nine. The Polyakov algorithm smoothes sharp curves and sudden changes in a signature, e.g., high frequency signature components. But this compression technique cannot distinguish between deliberate sharp curves in a signature, as opposed to sharp-appearing curves that are introduced by the digitizing process. For example, the genuine signature of an user-signer inflicted with palsy may include jittery lines. Unless a decompressed version of the genuine signature reproduces the jittery lines, verification is difficult. Such a signature would not fare well when compressed using the Polyakov method. Further, the Polyakov method is rather slow, taking typically many seconds to compress a signature.
Smoothing and filtering techniques are known in the art to remove compression-induced distortion and jaggedness. However, the use of such techniques should be minimized to reduce the risk of altering the original form of the signature in a significant manner. Further, in the case of a palsied user's signature, such smoothing signal processing would be counter-productive.
To summarize, when used to verify signatures for commercial or other legally binding transactions, it is important that device 10 or host system 80 be able to faithfully reproduce a high resolution image of a signature from compressed data. The original signature data should not be altered, which is to say that compression should be lossless, not lossy. Further, in a legally binding transaction, it is highly desirable to retain the original form of the signature for verification purposes.
Thus, there is a need for a compression technique that can rapidly handle a large volume of signature data, without altering the original form of the signature data. Such a compression technique should therefore be lossless, should provide a good compression ratio without introducing distortion, and preferably should be rapidly executable. Further, such a compression technique should provide a simple, preferably transparent, user interface.
The present invention provides such a compression technique and a device for implementing such compression.